contents

🌳 코딩 테스트를 위한 그래프 & 트리 알고리즘 – 심층 가이드와 예제

1. 그래프(Graph) 알고리즘

a. 기본 개념

• 그래프(Graph) 는 정점(Vertex) 과 간선(Edge) 으로 구성됩니다.
• 그래프 유형:
  • 방향 그래프(Directed): 간선에 방향 존재
  • 무방향 그래프(Undirected)
  • 가중치 그래프(Weighted) / 비가중치 그래프(Unweighted)
  • 유향/무향, 연결/비연결
  • 사이클 존재(Cyclic) / 무사이클(Acyclic)

b. 핵심 그래프 순회(Traversal) 알고리즘

DFS (Depth-First Search, 깊이 우선 탐색)

• 가능한 한 깊이 들어갔다가, 더 이상 진행할 수 없으면 되돌아오는 방식
• 스택(Stack) 또는 재귀(Recursion) 사용
• 활용: 사이클 탐지, 연결 요소 탐색, DAG에서 위상 정렬, 미로 탐색

void dfs(int node, boolean[] visited, List<Integer>[] adj) {
    visited[node] = true;
    for (int next : adj[node]) {
        if (!visited[next]) dfs(next, visited, adj);
    }
}

BFS (Breadth-First Search, 너비 우선 탐색)

• 인접한 노드를 먼저 모두 방문한 후, 그 다음 레벨로 진행
• 큐(Queue) 사용
• 활용: 비가중치 그래프 최단경로, 레벨 탐색, 이분 그래프 판별

void bfs(int start, List<Integer>[] adj, boolean[] visited) {
    Queue<Integer> queue = new LinkedList<>();
    queue.add(start);
    visited[start] = true;
    while (!queue.isEmpty()) {
        int node = queue.poll();
        for (int neighbor : adj[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                queue.add(neighbor);
            }
        }
    }
}

다익스트라(Dijkstra) 알고리즘

• 가중치가 모두 양수인 그래프에서 하나의 시작점으로부터 모든 정점까지의 최단거리 계산
• 우선순위 큐(PriorityQueue) 사용

PriorityQueue<Pair> pq = new PriorityQueue<>((a, b) -> a.dist - b.dist);
pq.add(new Pair(source, 0));
while (!pq.isEmpty()) {
    Pair p = pq.poll();
    // 인접한 노드 검사 후, 더 짧은 경로 발견 시 갱신 및 pq에 추가
}

그 외 중요한 그래프 알고리즘

• 위상 정렬(Topological Sort) – 방향성 비순환 그래프(DAG)에서 순서 결정
• 유니온 파인드(Union-Find, Disjoint Set) – 집합 병합/사이클 탐지
• 최소 신장 트리(MST) – Kruskal / Prim 알고리즘 (모든 노드를 연결하는 최소 비용)

2. 트리(Tree) 알고리즘

a. 기본 개념

• 트리(Tree): 사이클이 없는 계층적 자료 구조
• **루트 노드(Root)**와 자식 노드(Children) 구성
• 이진 트리(Binary Tree): 각 노드가 최대 2개의 자식(Left/Right)을 가짐
• 이진 탐색 트리(BST): 왼쪽 < 부모 < 오른쪽 순서 유지

b. 트리 순회 방법

중위(Inorder), 전위(Preorder), 후위(Postorder) 순회

• Inorder (LNR): 왼쪽 → 노드 → 오른쪽 (BST 탐색 시 오름차순)
• Preorder (NLR): 노드 → 왼쪽 → 오른쪽
• Postorder (LRN): 왼쪽 → 오른쪽 → 노드

void inorder(TreeNode root) {
    if (root == null) return;
    inorder(root.left);
    System.out.print(root.val + " ");
    inorder(root.right);
}

레벨 순서 순회(Level Order, BFS)

• 루트부터 시작해 같은 레벨의 노드들을 차례대로 방문

void levelOrder(TreeNode root) {
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        System.out.print(node.val + " ");
        if (node.left != null) queue.add(node.left);
        if (node.right != null) queue.add(node.right);
    }
}

자주 쓰이는 트리 알고리즘

• 최소 공통 조상(LCA, Lowest Common Ancestor)
• 트리 균형화(AVL, Red-Black Tree)
• 힙(Heap) – 우선순위 큐 구현, 힙 정렬

3. 코딩 테스트에서 자주 나오는 문제 예시

그래프(Graph):

• 두 노드 간 모든 경로 찾기 (DFS/백트래킹)
• 최단 경로 (BFS/다익스트라)
• 사이클 감지 (DFS/유니온 파인드)
• 위상 정렬 (BFS/DFS)

트리(Tree):

• 이진 트리 뒤집기
• BST 검증
• LCA 찾기
• 트리 최대 경로 합
• 트리 직렬화/역직렬화

4. 요약 표

💡 Tip:

• DFS/BFS는 그래프 탐색 + 트리 순회 문제 모두에서 자주 등장하니 반복 숙지
• 트리 문제에서는 재귀 패턴 이해, 그래프 문제에서는 큐/스택 자료구조 사용법 숙지 필수
• 연결/비연결 그래프 모두 고려, 사이클 여부 체크 습관화

🌐 그래프(Graph) 대표 출제 문제

1. 최단 경로 찾기

• BFS: 비가중치 그래프에서 시작점 → 모든 노드까지 최단 거리
  • (예: 미로 문제, 네트워크 hop 수)
• Dijkstra: 가중치(양수) 그래프에서 시작점 → 최소 비용
  • (예: 지도 경로, 소셜 네트워크 최소 연결)

2. 사이클 감지

• DFS + 방문 배열
  • 무방향/방향 그래프 모두
  • (예: 커넥션 루프 체크, 순환 참조 검출)
• Union Find(Disjoint Set)
  • 무방향 그래프 사이클 빠른 검출

3. 최소 신장 트리(MST)

• Kruskal/ Prim 알고리즘
  • 모든 노드 연결 최소 비용
  • (예: 통신망 구축 비용, 도시 도로망 연결)

4. 위상 정렬(Topological Sort)

• 방향성 비순환 그래프(DAG)에서 순서 정하기
  • (예: 작업 순서, 수강 과목/프로젝트 선후관계)

5. 모든 경로/도달 여부 찾기

• DFS/BFS 활용
  • 두 노드 사이의 모든 경로, 단일 경로, 최대 경로 등
  • (예: 트리 분기 경로, 그래프 연결성 확인)

6. 그래프 연결 요소 개수

• DFS/BFS로 방문 안 된 노드 그룹 카운트
  • (예: 섬 개수, 네트워크 컴포넌트)

🌳 트리(Tree) 대표 출제 문제

1. 트리 순회(Traversal)

• 중위/전위/후위 (재귀/반복)
  • (예: 이진 트리 출력, 노드 탐색 등)

2. 트리 최대/최소 경로 합

• DFS로 모든 루트-리프 경로 탐색
  • (예: 트리의 최대/최소 sum 경로)

3. BST 검증/구성

• 이진 탐색 트리(BST)인지 체크, BST 생성/삽입/삭제
  • (예: 트리로 정렬, 트리 검색 최적화)

4. 트리 뒤집기/리버스

• 트리 구조 좌우 반전(거울 트리)
  • (예: LeetCode 226)

5. 최소 공통 조상(LCA) 찾기

• 두 노드의 가장 아래(공통) 조상 찾기
  • (예: 리눅스 경로, 권한 트리)

6. 트리 직렬화/역직렬화

• 트리/그래프를 스트링(리스트 등)으로 변환/복원
  • (예: JSON/XML 구조 변환, 데이터 저장)

✅ 요약 표

💡 실전 팁

• BFS/DFS 정석 구현은 반드시 암기 및 손코딩 연습!
• 그래프 입력(인접행렬 vs 인접리스트), 트리 노드 구조에 친숙해져야 함
• 트리/그래프 문제 모두 자료구조와 알고리즘 선택이 관건
• 반례 만들며 테스트! (비연결, 사이클, 빈 트리, 경로 없음 등)

references